/**
 * https://leetcode-cn.com/problems/house-robber/
 * 打家劫舍
 * @param nums 
 */
export const rob = (nums: number[]): number => {

    // dp[i] 表示劫到i家的最大金额
    // 状态转移方程: dp[i] = max{dp[i - 2] + num[i], dp[i - 1]}, 间隔的前一家和间隔两家的前一家
    const len = nums.length;
    if (len === 0) return 0

    // 数组只有一项
    if (len === 1) return nums[0]

    // 前前一家
    let pp = nums[0]



    
    // 前一家
    //! 默认为第一家和第二家的金额最大值
    let p = Math.max(nums[0], nums[1])


    let ans = p
    for (let i = 2; i < len; i++) {
        // 前前一家加上当前的金额和前一家比较
        ans = Math.max(pp + nums[i], p)

        // 更改前一家和前前一家
        pp = p
        p = ans
    }

    return ans
};


const rob3 = (nums: number[]): number => {

    // dp[i] 表示劫到i家的最大金额
    // 状态转移方程: dp[i] = max{dp[i - 2] + num[i], dp[i - 1]}, 间隔的前一家和间隔两家的前一家
    const len = nums.length;
    if (len === 0) return 0

    // 数组只有一项
    if (len === 1) return nums[0]

    const dp: number[] = new Array(len)
    dp[0] = nums[0]

    //! 默认为第一家和第二家的金额最大值
    dp[1] = Math.max(nums[0], nums[1])


    for (let i = 2; i < len; i++) {
        // 前前一家加上当前的金额和前一家比较
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
    }

    return dp[len - 1]
};


const rob2 = (nums: number[]): number => {

    // dp[i] 表示劫到i家的最大金额
    // 状态转移方程: dp[i] = max{dp[i - 2], dp[i - 3]} + nums[i], 间隔的前一家和间隔两家的前一家

    const len = nums.length;

    // 数组只有一项
    if (len === 1) return nums[0]

    const dp: number[] = new Array(len + 1)
    dp[0] = 0
    dp[1] = nums[0]
    dp[2] = nums[1]

    // 默认先比较他们的最大值
    let max = Math.max(dp[1], dp[2])

    for (let i = 2; i < len; i++) {
        // 比较前一家和前前一家的最大值, 加上当前这家
        dp[i + 1] = Math.max(dp[i - 1], dp[i - 2]) + nums[i]

        max = Math.max(max, dp[i + 1])
    }

    return max;
};

console.log(rob([1, 2, 3, 1]))